#pragma once

#include <iostream>
#include <vector>

namespace solution_081
{

class Solution
{
public:
    bool search(const std::vector<int>& nums, int target)
    {
        if (nums.empty())
            return false;
        int i = 0;
        for (; i + 1 < (int)nums.size(); ++i) {
            if (nums.at(i) > nums.at(i + 1))
                break;
        }
        return binary_search(nums.cbegin(), nums.cbegin() + i + 1, target) ||
               binary_search(nums.cbegin() + i, nums.cend(), target);
    }

private:
    template <typename InputIt>
    bool binary_search(InputIt first, InputIt last, int target)
    {
        while (first != last) {
            auto mid = first + std::distance(first, last) / 2;
            if (*mid == target)
                return true;
            if (target < *mid)
                last = mid;
            else
                first = mid + 1;
        }
        return false;
    }
};

}  /* namespace solution_081 */
